0823. 带因子的二叉树【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

给出一个含有不重复整数元素的数组 arr，每个整数 arr[i] 均大于 1。

用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个？答案可能很大，返回 对 10^9 + 7 取余 的结果。

---

示例 1：

输入: arr = [2, 4]
输出: 3
解释: 可以得到这些二叉树: [2], [4], [4, 2, 2]

示例 2：

输入: arr = [2, 4, 5, 10]
输出: 7
解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

---

提示：

• 1 <= arr.length <= 1000
• 2 <= arr[i] <= 10^9
• arr 中的所有值 互不相同

2. 🎯 s.1 - 动态规划

c

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

int numFactoredBinaryTrees(int* arr, int arrSize) {
    long long MOD = 1000000007;
    qsort(arr, arrSize, sizeof(int), cmp);
    long long* dp = (long long*)calloc(arrSize, sizeof(long long));
    long long res = 0;
    for (int i = 0; i < arrSize; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if ((long long)arr[j] * arr[j] > arr[i]) break;
            if (arr[i] % arr[j] != 0) continue;
            int target = arr[i] / arr[j];
            int lo = j, hi = i - 1, found = -1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (arr[mid] == target) { found = mid; break; }
                if (arr[mid] < target) lo = mid + 1; else hi = mid - 1;
            }
            if (found != -1) {
                long long cnt = dp[j] * dp[found] % MOD;
                if (arr[j] != target) cnt = cnt * 2 % MOD;
                dp[i] = (dp[i] + cnt) % MOD;
            }
        }
        res = (res + dp[i]) % MOD;
    }
    free(dp);
    return (int)res;
}

js

/**
 * @param {number[]} arr
 * @return {number}
 */
var numFactoredBinaryTrees = function (arr) {
  const MOD = 1e9 + 7
  arr.sort((a, b) => a - b)
  const dp = new Map()
  let res = 0
  for (const x of arr) {
    dp.set(x, 1)
    for (const a of arr) {
      if (a * a > x) break
      if (x % a === 0 && dp.has(x / a)) {
        const b = x / a
        let cnt = (dp.get(a) * dp.get(b)) % MOD
        if (a !== b) cnt = (cnt * 2) % MOD
        dp.set(x, (dp.get(x) + cnt) % MOD)
      }
    }
    res = (res + dp.get(x)) % MOD
  }
  return res
}

py

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        arr.sort()
        dp = {}
        res = 0
        for x in arr:
            dp[x] = 1
            for a in arr:
                if a * a > x: break
                if x % a == 0 and x // a in dp:
                    b = x // a
                    cnt = dp[a] * dp[b] % MOD
                    if a != b: cnt = cnt * 2 % MOD
                    dp[x] = (dp[x] + cnt) % MOD
            res = (res + dp[x]) % MOD
        return res

• 时间复杂度：$O(n^2\log n)$，其中 n 是数组长度
• 空间复杂度：$O(n)$

算法思路：

• 排序后用 DP，$dp[x]$ 表示以 x 为根的二叉树数量
• 枚举因子对 $(a,b)$ 使得 $a\times b=x$，$dp[x]+=dp[a]\times dp[b]$